package com.longshine.arthmetic.tree;

import com.longshine.arthmetic.DrawableApp;
import com.longshine.arthmetic.Node;

/**
 * 排序二叉树,父结点权重大于左结点，小于右结点
 *  
 *
 * @classname   SortTree.java 
 * @author      YitianC
 * @version     Revision: 1.1,  Date: 2008/05/14 01:43:47  
 * @history     
 *              Mar 12, 2012 6:11:54 PM  
 *
 */
public class SortTree{

	protected Node root; //根结点
	public Node getRoot(){
		return root;
	}
	/**
	 * 
	 * 添加结点 
	 * 
	 * @param n
	 * @author      YitianC 
	 * @history 
	 *              YitianC Mar 13, 2012 4:56:57 PM
	 */
	public void addNode(Node n){
		if(root == null){
			root = n;
			return;
		}
		Node t = root;
		Node p = root;
		int r = 0;
		//找到要插入适合位置　
		while(t != null){
			r = t.compare(n);
			p = t;
			if(r<0){
				t = t.right;
			}
			else{
				t = t.left;
			}
		}
		if(p == null){
			p = root;
		}
		r = p.compare(n);
		if(r<0){
			p.right = n;
			n.parent = p;
		}
		else{
			p.left = n;
			n.parent = p;
		}
	}
	/**
	 * 
	 * 删除结点 
	 * 
	 * @param n　要删除的结点
	 * @author      YitianC 
	 * @history 
	 *              YitianC Mar 13, 2012 4:57:08 PM
	 */
	public void remove(Node n){
		if(n.parent==null){
			root = null;
			return;
		}
		if(n.right == null){
			n.parent.right = n.left;
			if(n.left != null){
				n.left.parent = n.parent;
			}
			return;
		}
		/*
		 * n的右结点的左叶子结点成为左结点的父结点 
		 */
		Node t = n.right;
		while(t.left!= null){
			t = t.left;
		}
		
		t.left = n.left;
		n.left.parent = t;
		if(n.parent.left==n){
			n.parent.left = n.right;
		}
		else{
			n.parent.right = n.right;
		}
		n = null;
	}
	
	public static void main(String args[]){
		SortTree t = new SortTree();
		Node n = new Node(20);
		t.addNode(n);
		n = new Node(50);
		t.addNode(n);
		n = new Node(19);
		Node t1 = n;
		t.addNode(n);
		n = new Node(15);
		t.addNode(n);
		n = new Node(30);
		t.addNode(n);
		n = new Node(17);
		t.addNode(n);
		n = new Node(5);
		t.addNode(n);
		n = new Node(3);
		t.addNode(n);
		n = new Node(11);
		t.addNode(n);
		n = new Node(60);
		t.addNode(n);
		n = new Node(25);
		t.addNode(n);
		n = new Node(21);
		t.addNode(n);
/*		n = new Node(4);
		t.addNode(n);
		n = new Node(9);
		t.addNode(n);
		n = new Node(18);
		t.addNode(n);
		n = new Node(7);
		t.addNode(n);
		n = new Node(22);
		t.addNode(n);
		n = new Node(6);
		t.addNode(n);
		n = new Node(8);
		t.addNode(n);
		n = new Node(20);
		t.addNode(n);
		n = new Node(17);
		t.addNode(n);
		n = new Node(32);
		t.addNode(n);
		n = new Node(35);
		t.addNode(n);
		n = new Node(28);
		t.addNode(n);*/
	//	t.remove(t1);
		DrawableApp da = new DrawableApp();
		System.out.println("总结点数为"+da.getNodeCount(t));
		System.out.println("树高度为"+da.getTreeHeight(t));
		da.drawTree(t);
		System.out.println(t);
		
	}
}
